package codingforgreat.lchot150;

public class Lc062 {
    public int uniquePaths(int m, int n) {
        //dp 不写了
        int right = n - 1;
        int all = m + n - 2;
        long o1 = 1;
        long o2 = 1;
        for(int i = all - right + 1, j = 1;j <= right;j++,i++){
            o1 *= i;
            o2 *= j;
            long g = gcb(o1,o2);
            o1 /= g;
            o2 /= g;
        }
        return (int) (o1/o2) ;

    }
    public long gcb(long a,long b){
        return b == 0 ? a : gcb(b,a % b);
    }
}
